Tremissis được đúc mang tên Aelia Verina, vợ và sau là góa phụ của Hoàng đế Leo I. Là chị của Basiliscus, Verina đã giúp em trai mình thăng quan tiến chức trong sự nghiệp quân sự và chính trị — ngay cả khi miễn cưỡng ủng hộ ông đoạt lấy ngôi vị Hoàng đế.

Xuất thân từ vùng Balkan,[1] đại khái thì Basiliscus là em trai Aelia Verina, vợ của Hoàng đế Leo I. Có lập luận cho rằng Basiliscus có mối quan hệ họ hàng với thủ lĩnh của tộc Heruli là Odoacer. Liên kết này được dựa trên việc giải thích một đoạn sử liệu của John xứ Antioch (209.1) mà nói rằng Odoacer và Armatus, cháu của Basiliscus đều là anh em với nhau.[2] Tuy nhiên, không phải tất cả các học giả đều chấp nhận cách giải thích này, bởi vì các nguồn tài liệu này không nói bất cứ điều gì về nguồn gốc ngoại quốc của Basiliscus.[3] Theo sử liệu cho biết thì Basiliscus có một người vợ là Zenonis và ít nhất một người con trai tên Marcus.

Basiliscus bắt đầu cuộc đời binh nghiệp của ông dưới thời Leo I. Hoàng đế ban cho người em rể quyền cao chức trọng với chức vụ chỉ huy trưởng quân đoàn xứ Thracia.[4] Chính tại đây mà Basiliscus đã dẫn đầu một chiến dịch quân sự thành công bình định người rợ Bulgar vào năm 463. Sau đó ông kế nhiệm Rusticius làm magister militum per Thracias (Đại tướng quân xứ Thracia) vào năm 464, và đã đạt được một số thành công trong cuộc chiến chống lại người rợ Goth và Hun xâm phạm lãnh biên ải vào năm 466 hoặc 467.[5]

Cũng vì vậy mà Basiliscus dần được Hoàng đế tín nhiệm. Lại thêm được Verina tiến cử nhằm ý định nâng đỡ sự nghiệp quân sự và chính trị của Basiliscus nhằm mưu lợi cho riêng mình, ít lâu sau Leo phong chức chấp chính quan cho ông vào năm 465 và dần thăng lên cấp bậc patricius.[6] Tuy nhiên, việc thăng quan tiến chức của ông chẳng lâu sau đã sớm bộc lộ ý đồ mưu tính đại sự.[1]